package demo23;

//计数排序；找到数组最大值与最小值确定计数数组的长度，建好计数数组，利用对原数组的遍历，将出现的元素减去最小值作为计数数组元素的下标，出现几次，对应计数数组对应元素（次数）加加
//出现次数对应数已有序之后还原到元素组，元素等于最小值加下标据次数还原
public class Sort3 {
        public void countSort(int[] array){
            int min=array[0];
            int max=array[0];
            for(int i=0;i<array.length;i++){
                if(array[i]<min){
                    min=array[i];
                }
                if(array[i]>max){
                    max=array[i];
                }
            }
            int len=max-min+1;
            int[]count=new int[len];
            //相同值存入计数数组
            for(int i=0;i<array.length;i++){
                int index=array[i];
                count[index-min]++;
            }
            int index1=0;

            for(int i=0;i<count.length;i++){
                while(count[i]!=0){//弹出计数数组的每一个值对应多少次存入原数组
                    array[index1]=min+i;
                    index1++;
                    count[i]--;
                }
            }

        }
}
